// https://www.lintcode.com/problem/is-subsequence/my-submissions

class Solution {
public:
    /**
     * @param s: the given string s
     * @param t: the given string t
     * @return: check if s is subsequence of t
     */
    // bool isSubsequence(string &s, string &t) {
    //     if (s.empty()) return true;
    //     if (t.empty()) return false; //注意！
        // int i = 0; 
        // int j = 0;
        // for (; i < t.length(); ++i)
        // {
        //     if (t[i] == s[j])
        //     {
        //         ++j;
        //         if (j == s.length())
        //             return true;
        //     }
        // }
        // return false;
    // }
    
    // follow up
    int find(vector<int> nums, int t, int start, int end)
    {
        while (start + 1 < end)
        {
            int mid = (end - start) / 2 + start;
            if (nums[mid] > t)
                end = mid;
            else
                start = mid;
        }
        // if (nums[start] > t) return start;
        // if (nums[end] > t) return end;
         if (nums[start] > t) return nums[start];
        if (nums[end] > t) return nums[end];
        return -1;
    }
    bool isSubsequence(string &s, string &t) {
        if (s.empty()) return true;
        if (t.empty()) return false; 
        map<char, vector<int>> record;
        // int back = 0; 注意！
        int back = -1;
        for (int i = 0; i < t.length(); ++i)
        {
            record[t[i]].push_back(i);
        }
        for (int i = 0; i < s.length(); ++i)
        {
            cout << s[i] << endl;
            if (record.find(s[i]) == record.end()) 
                return false;
            int idx = find(record[s[i]], back, 0, record[s[i]].size() - 1);
            cout << idx << endl;
            if (idx == -1)
                return false;
            back = idx;
        }
        return true;
    }
};